% -*- coding:utf-8 -*-

\documentclass{article}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[spanish]{babel}

\usepackage[bookmarks, hyperfootnotes=false, colorlinks=true,%
            urlcolor=blue, linkcolor=black,  citecolor=black,%
            pagecolor=black, anchorcolor=black, breaklinks=true]{hyperref}

\usepackage{enumerate}
\usepackage{eurosym}
\usepackage{graphicx}
\usepackage{times}
\usepackage{color}
\usepackage{array}
\usepackage{colortbl}
\usepackage{longtable}

\usepackage{fancyhdr}
\usepackage{fancybox}
\usepackage{listings}
\usepackage{subfigure}
\usepackage{hyperref}
\usepackage{tikz}

\usepackage{epsfig}
\usepackage{float}
\usepackage{amsmath}
\usepackage{lscape}

\setlength{\headheight}{16pt}
\setlength{\oddsidemargin}{17pt}
\setlength{\textwidth}{420pt}
\setlength{\topmargin}{0pt}
\setlength{\textheight}{600pt}
\setlength{\marginparwidth}{55pt}


\newcommand{\fsm}{\emph{FSM}}
\newcommand{\ice}{\emph{ICE}}
\newcommand{\icefield}{\emph{IceField}}
\newcommand{\slice}{\emph{Slice}}

\pagestyle{fancy}

\renewcommand{\footrulewidth}{0.5pt}

\fancyhead[R]{Práctica 1-Tarea 5}
\fancyhead[L]{Inteligencia Artificial}
\fancyfoot[R]{Manuel J. Abaldea Gª-Pliego}
\fancyfoot[L]{Mejora de Soluciones}


\newenvironment{float_code} {
      \begin{lst}
      }
      {
      \end{lst}
      }


\newfloat{lst}{H}{lop}[section]
\floatname{lst}{Listado}
\floatplacement{codigo}{!htb}
\floatstyle{plain}


\begin{document}

\begin{center}
\begin{Large}\textit{\textquotedblleft
Inteligencia Artificial \ \ Práctica 1
\textquotedblright}\end{Large}
\end{center}

\vspace*{0.5cm}

\begin{flushleft}
\begin{large}
\textit{
Alumno: Manuel J. Abaldea Gª-Pliego
}
\end{large}
\end{flushleft}

\vspace*{1cm}

\section*{Tarea 1: Tecnologías utilizadas y definición de estado y acción}
\subsection*{Tecnologías utilizadas y definición de estado y acción.}
\subsubsection*{Tecnologías usadas}
Para la realización de esta primera práctica utilizaré el lenguaje de
programación \emph{C++}.

\emph{C++} nos proporciona varias ventajas como
que es un lenguaje orientado a objetos, esto facilita la creación de
sistemas complejos proporcionando robustez y legibilidad en el
código. ¿Por qué no utilizar otro lenguaje orientado a objetos como
\emph{Java}? Por didáctica, he trabajado mucho menos con \emph{C++} y
quiero aprovechar este trabajo para practicar. Otra gran ventaja, que
se puede volver en mi contra, es el manejo de punteros y memoria; esto
nos proporciona un mejor control de la memoria y administración de los
recursos pero puede complicar el código si no se tiene suficiente
experiencia. También están las típicas ventajas de: es muy utilizado
y hay muchos tutoriales, existen muchas librerías, es compatible con
las de C, etc.

Para manipular las imágenes utilizaré una librería propia. Guardando
la imagen como \emph{PGM} en \emph{ASCI} puedo tomar la imagen como un
texto plano y trabajar con ella, de modo que una librería simple que
lea las cadenas de texto y obtenga la información necesaria para
trabajar es suficiente. Esto dará simplicidad a la práctica y bien
programada puede incluso ahorrar recursos.

\subsubsection*{Problema de espacio de estados simple.}
Para definir un estados utilizaremos:
\begin{itemize}
\item posición: en el eje X e Y
\end{itemize}

De modo que un estado sería: $\{X,Y\}$

Los actuadores serían los movimientos, considerando que comenzamos
desde la esquina superior izquierda:
\begin{itemize}
\item mover izquierda: X-1
\item mover derecha: X+1
\item mover abajo: Y+1
\item mover arriba: Y-1
\end{itemize}

\clearpage

El motivo de comenzar desde la esquina superior izquierda es que
utilizaré una matriz de enteros para representar el mapa, de modo que
de este modo las coordenadas X e Y coincidirán con las coordenadas de
la matriz, y el valor en dicha coordenada será el coste en escala de
grises (0-15) de la posición.
Antes de que los actuadores transformen el estado tendremos en cuenta:
\begin{itemize}
\item mover izquierda: solo si X-1 > 0
\item mover derecha: solo si X+1 < anchura del mapa
\item mover abajo: solo si Y+1 < profundidad del mapa
\item mover arriba: solo si Y-1 > 0
\end{itemize}

Multimap es un contenedor asociativo que contiene una lista ordenada de pares clave-valor. La clasificación se realiza de acuerdo con la Compare función de comparación, aplicada a las teclas. Las operaciones de búsqueda, inserción y eliminación tiene complejidad logarítmica .

El orden de los pares de clave y valor cuyas claves comparar equivalente es el orden de inserción y no cambia. (ya que C + +11)

std::multimap cumple los requisitos de Container,
AllocatorAwareContainer, AssociativeContainer y ReversibleContainer .

Para el almacenamiento de los nodos durante la ejecución utilizaré un
contenedor de datos asociativo \emph{multimap}  de \emph{C++}. Este
tipo de contenedor almacena pares clave-valor y los ordena
automáticamente por clave. Proporcionará la capacidad de acceso a los
nodos ya ordenados sin esfuerzo con una complejidad (según la
documentación) logarítmica).

\subsubsection*{Estructuras necesarias.}
Será necesario un árbol con los nodos de nuestro problema y una cola
con prioridad que será la frontera.
En nuestra implementación la cola con prioridad será el
\emph{multimap}. El orden de prioridad vendrá dado por la clave del
par valor-clave almacenado. Como clave indicaremos el valor por el
cual se ordenarán los nodos (profundidad o coste según el tipo de búsqueda).

Durante la ejecución del programa, en el proceso de búsqueda, la {\bf
  paginación en memoria} está pensada de modo que toda la frontera
esté almacenada en memoria primaria, para no saturarla se manejarán
todas las referencias a los datos mediante punteros realizando el
menor número de copias de datos posibles. Se optará por utilizar
\emph{SmartPointers} para que los datos borrados de la frontera y no
referenciados se limpien automáticamente.

\clearpage

\section*{Tarea 2: Test de la estructura de datos}
\subsection*{Estructura de datos para la cola con prioridad}
La estructura de datos para nuestra base de datos será la siguiente:
\begin{verbatim}
class Nodo{
  int CoX;
  int CoY;
  int cost;
  int prof;
  Nodo* father;
  float f;
 public:
  Nodo();
  ~Nodo();
  Nodo(int CoX_v, int CoY_v, int cost_v, int prof,
       Nodo* father_v, float f_v);
  int get_coX()const;
  int get_coY()const;
  int get_cost()const;
  int get_prof()const;
  Nodo* get_father()const;
  float get_f()const;
  void set_coX(int CoX_v);
  void set_coY(int CoY_v);
  void set_cost(int cost_v);
  void set_prof(int prof_v);
  void set_father(Nodo* father_v);
  void set_f(float f_v);
  void set(int CoX_v, int CoY_v, int prof_v, Nodo* father_v);
  void toString()const;
};
\end{verbatim}
Se almacenará el puntero a la estructura en un multimap, donde la
clave será el valor f:
\begin{verbatim}
  multimap<int,Nodo*> frontera;
  frontera.insert(pair<float,Nodo*>(nodo.get_f(), &nodo));
\end{verbatim}


\subsection*{Evaluar la capacidad de la estructura}
Para evaluar la estructura se ha utilizado el siguiente código:

\begin{verbatim}
int main(){
  clock_t ini, fin;
  int i;
  ini = clock();
  Nodo inicial(0,0,0,0,NULL,0);
  float(*p_func)(Nodo&, int*);
  multimap<int,Nodo*> frontera;
  for (i=0;i<Num_nodos;i++)
    frontera.insert(pair<float,Nodo*>(inicial.get_f(), &inicial+1));

  ini = clock() -ini;
  cout<< "Tiempo insercion: " << (((float)ini)/CLOCKS_PER_SEC) << endl;

  return 0;
}
\end{verbatim}
Y los resultados han sido los siguientes:
\begin{itemize}
\item 100000000 nodos en 244.06 segundos
\item Número de nodos hasta colapsar: CALCULAR
\item Tiempo medio de inserción de un nodo: 0,000002441 segundos.
\end{itemize}

\clearpage

\subsection*{Algoritmo de búsqueda de soluciones}
Se interpreta que el algoritmo devuelve un vector con los
identificadores de los nodos que componen la solución. Si existe un
único nodo con identificador 0 significará que no se ha encontrado
solución.

\begin{verbatim}
int* Busqueda (mapa_problema){
     frontera = Frontera(mapa_problema);   //nodo inicial
     while front.lenght > 0{
          nodo_actual = frontera.pop();    //extraer y eliminar nodo
          if nodo_actual.coordX = MAX_W and nodo_actual.coordY = MAX_D{
               sol_nodo = nodo_actual;
               break;
          }
          nodo_actual.expand(frontera);
     }
     if sol_nodo == NULL
          return 0;
     else
          return CrearSol(sol_nodo)
\end{verbatim}

\clearpage

\section*{Tarea 3: Construir función BÚSQUEDA}
Resultados:

 \begin{tabular}[!ht]{|c|c|c|c|} \hline
    \textbf{Algoritmo} & \textbf{Tamaño imagen} & \textbf{nodos
      expandidos} & \textbf{tiempo en hallar solución} \\ \hline
    Anchura & 500x500 & 250000 & 0.18 segundos  \\ \hline
    Anchura & 1000x1000 & 1000000 & 0.50 segundos  \\ \hline
    Coste Uniforme & 1000x1000 & 988871 & 0.62 segundos \\ \hline
    Coste Uniforme & 500x500 & 249911 & 0.15 segundos \\ \hline
    Profundidad & 1000x1000 & 3995 & 0.06 segundos \\ \hline
    Profundidad & 500x500 & 1995 & 0.01 segundos \\ \hline
    Prof. Acotada & 1000x1000 & 3995 & 0.06 segundos \\ \hline
    Prof. Acot. Iterativa & 1000x1000 & 10885 & 0.21 segundos  \\ \hline
  \end{tabular}

Para la profundidad acotada se ha tomado una cota de 2000, ya que con
cotas inferiores a 1998 no encontraba solución. Y para la profundidad
iterativa se han tenido encuenta estos datos para utilizar en la
prueba una profundidad de 1000, aumento de cota de 500 y 3 iteraciones.

\section*{Tarea 4: Búsqueda heurística}
Ya que teníamos definida la función de evaluación como un puntero a
función, para añadir estos algoritmos en el código implementado el
principal cambia a sido incluir las funciones en el \emph{switch} de
selección:
\begin{verbatim}
switch(estrategia){
  case 1: // anchura
    p_func = F_Anchura;
    break;
  case 2: // coste uniforme
    p_func = F_CosteU;
    break;
  case 3: // profundidad
    p_func = F_Prof;
    break;
  case 4: // A* Euclídea
    p_func = F_Euclidea;
    break;
  case 5: // A* Manhattan
    p_func = F_Manhattan;
    break;
  case 6: // profundidad acotada
    p_func = F_Prof;
    break;
  case 7: // profundidad iterativa
    p_func = F_Prof;
    break;
  default:
    cout << "Opcion incorrecta en P_FUNC!!!!" << endl;
    return false;
  }
\end{verbatim}

\clearpage

Y añadir las correspondientes funciones:

\begin{verbatim}
float F_Euclidea(Nodo &nodo_aux, int* posFin){
  float dist, cost;
  dist = sqrt(pow((posFin[0] - nodo_aux.get_coX()),2) +
	      pow((posFin[1] - nodo_aux.get_coY()),2));
  cost = nodo_aux.get_cost() + dist;
  return cost;
}
float F_Manhattan(Nodo &nodo_aux, int* posFin){
  float dist, cost;
  dist = abs(posFin[0] - nodo_aux.get_coX()) +
         abs(posFin[1] - nodo_aux.get_coY());
  cost = nodo_aux.get_cost() + dist;
  return cost;
}
\end{verbatim}

Los resultados han sido los siguientes:

 \begin{tabular}[!ht]{|c|c|c|c|c|} \hline
    \textbf{Algoritmo} & \textbf{Tamaño imagen} & \textbf{nodos
      expandidos} & \textbf{tiempo en hallar solución} & \textbf{coste}\\ \hline
    Coste Uniforme & 500x500 & 249911 & 0.35 segundos & 2484 \\ \hline
    Coste Uniforme & 1000x1000 & 988871 & 1.56 segundos & 7046 \\ \hline
    A* Euclídea & 500x500 & 262061 & 0.39 segundos & 2484 \\ \hline
    A* Euclídea & 1000x1000 & 1005172 & 1.72 segundos & 7046 \\ \hline
    A* Manhattan & 500x500 & 272232 & 0.40 segundos &  2484 \\ \hline
    A* Manhattan & 1000x1000 & 10053698 & 1.74 segundos &  7046 \\ \hline
  \end{tabular}

Destacar que, aunque los algoritmos \emph{A*} despliegan menos nodos
que el de \emph{Coste Uniforme} tardan más tiempo en encontrar el nodo
solución. Se achaca este tiempo al cómputo extra de cálculo.

\clearpage

Los algoritmos \emph{A*} obtienen la misma solución, pero esta
solución difiere de la obtenida con costo uniforme.

\begin{figure}[!h]
  \center
  \includegraphics[scale=0.4]{CO_image_out.png}
  \caption{Mapa 1000x1000. Solución con COSTO UNIFORME}
\end{figure}
\begin{figure}[!h]
  \center
  \includegraphics[scale=0.4]{A_image_out.png}
  \caption{Mapa 1000x1000. Solución con A*}
\end{figure}

\clearpage

\section*{Tarea 5: Mejora de Soluciones}
\subsection*{Estructura para almacenar solución}
Se ha optado por una estructura de pila (LIFO) para almacenar las
posiciones por las que va pasando la solución. El utilizar una pila es
por facilitar el almacenamiento de la información desde los nodos ha
la estructura solución, recordemos que para construir la solución los
nodos los recorremos hacia arriba, buscando el padre del nodo
objetivo.
También almacenaremos el coste total de la solución.
No se ha visto necesario almacenar más información ya que la
estructura pila(\emph{stack} en \emph{C++}) nos proporciona funciones que nos
retornan el número de nodos y si está vacía.

La estructura es la siguiente:
\begin{verbatim}

class Solucion{
  int cost;
  stack <pair<int,int> > posiciones;

 public:
  Solucion();
  ~Solucion();
  Solucion(stack<pair<int,int> > posiciones, int cost);
  stack <pair<int,int> > get_Pposiciones()const;
  pair<int,int> get_posicion()const;
  int get_cost()const;
  int size_posiciones()const;
  bool empty_posiciones()const;
  void set_posicion(pair<int,int> posicion_v);
  void set_cost(int cost_v);
  void pop_posicion();
  bool cortar(pair<int,int> p_corte, map<pair<int,int>, int> mapa);
  void concatenar_sol(stack <pair<int,int> > posiciones_c);
  void toString()const;
};
\end{verbatim}

A parte de las típicas funciones de retorno y de acceso (los sets y
gets) también se han implementados funciones que replican la
funcionalidades típicas de una pila como \emph{pop()}, \emph{empty()} o \emph{size()}.
Funciones un poco más específicas son las de cortar y concatenar,
creadas para facilitar la modificación de soluciones.
\begin{itemize}
\item bool cortar(...)

  Pasando como argumento una posición esta función retornará true si
  la posición está en la solución y desechará las posiciones desde la
  posición dada hasta la posición final.
\item void concatenar\_sol(...)

  Toma como argumento una pila de posiciones y las une a la solución actual.
\end{itemize}


\subsection*{Función que evalúa las soluciones}
Como no se ha indicado el tipo de valoración se ha optado por lo más
simple. La valoración dada es el coste por nodo.

\begin{verbatim}
double Val(Solucion solucion){
  double valoracion;

  valoracion = double(solucion.get_cost())/double(solucion.size_posiciones());

  return valoracion;
}
\end{verbatim}

\subsection*{Funciones que modifican las soluciones}
\subsubsection*{a) Modificar movimiento del camino}
Partiendo de una solución ya encontrada indicamos un punto por el cual
deba de pasar la nueva solución.
\begin{figure}[!h]
  \center
  \includegraphics{solucion_original.png}
  \caption{Solución de partida en mapa de 100x100. Solución con A*}
\end{figure}

Los que se han seguido han sido los siguientes:
\begin{itemize}
\item Hallar la posición perteneciente a la solución más cercana al
  punto deseado.
\item Cortar la solución, quedándose desde el origen hasta el punto
  dado.
    \begin{figure}[!h]
    \center
    \includegraphics{solucion_cortada.png}
    \caption{Solución cortada hasta el punto más cercano al dado.}
  \end{figure}
\item Buscar nuevo camino desde el punto de corte hasta el punto
  dado. Para esto utilizamos la función Busqueda() que tenemos
  construida, de modo que será necesario indicar el algoritmo que
  queremos aplicar (anchura,profundidad, A*, etc).
    \begin{figure}[!h]
    \center
    \includegraphics{solucion_m1.png}
    \caption{Solución concatenada hasta punto tado.}
  \end{figure}
\item Buscar nuevo camino desde el punto dado hasta el objetivo final.
    \begin{figure}[!h]
    \center
    \includegraphics{solucion_m2.png}
    \caption{Solución concatenada hasta punto objetivo.}
  \end{figure}
\item Concatenar los tres caminos en una única solución.
\end{itemize}




\subsubsection*{b)Determinar una circunferencia en el mapa por la cual
  no se pueda pasar}
Como en la función de búsqueda se marca el mapa para saber por qué
puntos se ha pasado se ha considerado como buena la idea de marcar el
mapa con la circunferencia dada y tratarla como se fuesen zonas no
accesibles (como los bordes).
    \begin{figure}[!h]
    \center
    \includegraphics{solucion_circunferencia.png}
    \caption{Solución modificada con obstáculo.}
  \end{figure}

En la interfaz gráfica se han definido estas modificaciones como
redirigir camino en el caso \emph{a)} y como obstaculizar camino en el caso
\emph{b)}.
\begin{figure}[!h]
  \center
  \includegraphics[scale=0.4]{ui.png}
  \caption{Interfaz gráfica del programa}
\end{figure}

\clearpage
\section*{Código implementado}
El código, así como el seguimiento de esta práctica está disponible en:

\url{https://code.google.com/p/ia-2012-13/}

\end{document}
